#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define Status int
#define QElemType int
#define OVERFLOW 0

//链队列的类型定义 
#define MAXQSIZE 100  //最大队列长度 
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
	QueuePtr front; //队头指针 
	QueuePtr rear;  //队尾指针 
}LinkQueue;


//算法3.16 链表的初始化  
Status InitQueue(LinkQueue &Q){
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front) exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}

//销毁链队列  算法思想：从队头结点开始，依次释放所有结点
Status DestoryQueue(LinkQueue &Q){
	while(Q.front){
		QNode *p = Q.front->next;
		free(Q.front);
		Q.front = p;
	}
	//方法2如下，不用指针p，用尾指针
	/*
	while(Q.front){
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	*/
	return OK;
} 

//算法3.17 将元素e入队
Status EnQueue(LinkQueue &Q, QElemType e){
	QNode *p = new QNode;
//	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;
	return OK;
} 

//算法3.17 将元素e出队
Status DeQueue(LinkQueue &Q, QElemType &e){
	if(Q.front == Q.rear) return ERROR;
	QNode *p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p) Q.rear = Q.front; //特殊情况，将最后一个元素删除后，空队列 
	delete(p);
	return OK;
}

//算法3.19 求链队列的队头元素
Status GetHead(LinkQueue Q, QElemType &e){
	if(Q.front == Q.rear) return ERROR;
	e = Q.front->next->data;
	return OK;
} 

int main(void){
	LinkQueue Q;
	InitQueue(*&Q);
	printf("初始化链队成功!\nQ.front = %p, Q.rear = %p\n", Q.front, Q.rear);
	cout<<"请输入入队元素个数：";
	int num;
	cin>>num;
	for(int i = 1;i <= num; i++){
		printf("请输入第%d个元素：", i);
		QElemType e;
		cin>>e;
		EnQueue(*&Q, e);
	}
	puts("\n-------------------------------\n出队中.......");
	while(Q.front != Q.rear){
		QElemType e;
		DeQueue(*&Q, *&e);
		cout<<"元素 "<<e<<" 出队了...\n"; 
	}
	return 0;
}